Given two sparse vectors, compute their dot product.
Implement class SparseVector:
SparseVector(nums)Initializes the object with the vectornumsdotProduct(vec)Compute the dot product between the instance of SparseVector andvec
A sparse vector is a vector that has mostly zero values, you should store the sparse vector efficiently and compute the dot product between two SparseVector.
Follow up: What if only one of the vectors is sparse?
Example 1:
Input: nums1 = [1,0,0,2,3], nums2 = [0,3,0,4,0] Output: 8 Explanation: v1 = SparseVector(nums1) , v2 = SparseVector(nums2) v1.dotProduct(v2) = 1*0 + 0*3 + 0*0 + 2*4 + 3*0 = 8
Example 2:
Input: nums1 = [0,1,0,0,0], nums2 = [0,0,0,0,2] Output: 0 Explanation: v1 = SparseVector(nums1) , v2 = SparseVector(nums2) v1.dotProduct(v2) = 0*0 + 1*0 + 0*0 + 0*0 + 0*2 = 0
Example 3:
Input: nums1 = [0,1,0,0,2,0,0], nums2 = [1,0,0,0,3,0,4] Output: 6
Constraints:
n == nums1.length == nums2.length1 <= n <= 10^50 <= nums1[i], nums2[i] <= 100
Average Rating: 4.79 (14 votes)
Solution
A sparse vector is a vector that has mostly zero values, while a dense vector is a vector where most of the elements are non-zero. It is inefficient to store a sparse vector as a one-dimensional array (Approach 1). Instead, we can store the non-zero values and their corresponding indices in a dictionary, with the index being the key (Approach 2). Alternatively, we can represent elements of a sparse vector as an array of pairs for each non-zero value. Each pair has an integer index and a numerical value (Approach 3).
A related question is LeetCode 311. Sparse Matrix Multiplication.
Approach 1: Non-efficient Array Approach
Intuition
We ignore the sparsity of the array and store the original array.
Algorithm
Complexity Analysis
Let n be the length of the input array.
-
Time complexity: O(n) for both constructing the sparse vector and calculating the dot product.
-
Space complexity: O(1) for constructing the sparse vector as we simply save a reference to the input array and O(1) for calculating the dot product.
Approach 2: Hash Set
Intuition
Store the non-zero values and their corresponding indices in a dictionary, with the index being the key. Any index that is not present corresponds to a value 0 in the input array.
Algorithm
Complexity Analysis
Let n be the length of the input array and L be the number of non-zero elements.
-
Time complexity: O(n) for creating the Hash Map; O(L) for calculating the dot product.
-
Space complexity: O(L) for creating the Hash Map, as we only store elements that are non-zero. O(1) for calculating the dot product.
Approach 3: Index-Value Pairs
Intuition
We can also represent elements of a sparse vector as a list of <index, value> pairs. We use two pointers to iterate through the two vectors to calculate the dot product.
Algorithm
Complexity Analysis
Let n be the length of the input array and L and L2 be the number of non-zero elements for the two vectors.
-
Time complexity: O(n) for creating the <index, value> pair for non-zero values; O(L+L2) for calculating the dot product.
-
Space complexity: O(L) for creating the <index, value> pairs for non-zero values. O(1) for calculating the dot product.
December 7, 2020 5:11 PM
I would like to propose an improvement in the Hashmap solution. Instead of traversing the hash maps of the first vector, choose the one with minimum length min(v1.keySet().length, v2.keySet().length)
I got this question at my FB onsite in August 2020. The interviewer did not accept my hashmap solution. He told me that hashing/lookups, while on surface look efficient, for large sparse vectors, hashing function takes up bulk of the computation that we might be better off with the first method. Wihile proposing hashmap/set solutions, take a minute to think about the complexity hashing function.
December 31, 2020 9:47 AM
Am I the only one didn't get the point of the medium level tag?
Last Edit: May 5, 2021 7:12 AM
Perf vs Efficiency
Has anyone found an algorithm that is both performant and Facebook-approved?
The "non-efficient array approach" performed best.
JavaScript Map, Object and Set performed horribly.
I did get a "tuple" (array of [index, value]) to perform a little better, 30% slower than array.
Using Array.reduce or switching to the smaller size collection made runtime worse.
// ARRAY
// Runtime: 100 ms, faster than 98.92%
// Memory Usage: 51 MB, less than 95.04%
function SparseVector(nums) {
return {
nums,
dotProduct: function(vec) {
let d = 0
for (let i = 0; i < vec.nums.length; i++) {
if (this.nums[i] && vec.nums[i]) d += this.nums[i] * vec.nums[i]
}
return d;
}
};
}
// "TUPLE"
// Runtime: 132 ms, faster than 42.89%
// Memory Usage: 53.4 MB, less than 62.50%
class SparseVector {
constructor(nums) {
this.nums = [...nums.entries()].filter(el => el[1] !== 0);
}
dotProduct(vec) {
let d = 0;
for(let [index, value] of vec.nums){
let num = this.nums.find(el => el[0] === index);
if(num) d += value * num[1];
}
return d;
}
}
// MAP
// 396 ms, faster than 5.17%
// Memory Usage: 71.3 MB, less than 5.17%
class SparseVector {
constructor(nums) {
this.nums = new Map([...nums.entries()].filter(el => el[1] !== 0));
}
dotProduct(vec) {
let d = 0;
this.nums.forEach((el, i) => {
if (vec.nums.has(i)) d += vec.nums.get(i) * el;
});
return d;
}
}
// OBJECT
// Runtime: 160 ms
// Memory Usage: 56.7 MB
function SparseVector(nums) {
return {
nums: nums.reduce((acc, el, i) => {
if(el !== 0) acc[i] = el;
return acc;
}, {}),
has: function(i){
return this.nums.hasOwnProperty(i);
},
dotProduct: function(vec) {
let d = 0;
for (let [i, v] of Object.entries(vec.nums)) {
if(this.has(i)) d += this.nums[i] * v;
}
return d;
}
};
}
For approach #1, we could optimize by continuing the loop when either of the array has a 0 (no need to calculate the product)
Last Edit: March 20, 2021 9:11 PM
I read the comments about FB onsite not accepting the hashmap solution. Could using linked lists be an additional option? I think it's the same time/space as these other solutions, but easier to code.
When you create the spare vector, iterate and generate a linked list of values != 0. Each node tracks its idx and val. That's O(N) time O(L) space to create the vectors.
For dot product, iterate over each linked list with a pointer. If the idx values don't match, move up the pointer with the lower idx value etc. It's O(min(L1, L2)) time O(1) space to calculate dot product. Now you don't have to worry about which linked list is shorter - you just stop when you reach the end of one of them.
My solution came at the bottom of time/space, but posting here anyway:
class VectorNode:
def __init__(self, idx, val):
self.idx = idx
self.val = val
self.next = None
class SparseVector:
def __init__(self, nums: List[int]):
self.list = None
curr = None
for idx, val in enumerate(nums):
if val != 0:
node = VectorNode(idx, val)
if not self.list:
self.list = node
curr = node
else:
curr.next = node
curr = node
# Return the dotProduct of two sparse vectors
def dotProduct(self, vec: 'SparseVector') -> int:
left = self.list
right = vec.list
total = 0
while left and right:
if left.idx == right.idx:
total += (left.val * right.val)
left = left.next
right = right.next
elif left.idx < right.idx:
left = left.next
else:
right = right.next
return total
The question doesn't make sense. There needs to be some practical use of such an approach. There's no better/worst solution in normal use case.
June 1, 2021 10:12 AM
class SparseVector:
def __init__(self, nums: List[int]):
# Time: O(M), Space: O(M) where M is the length of the vector
self.vector = {}
for idx, num in enumerate(nums):
if num!=0:
self.vector[idx] = num
# Return the dotProduct of two sparse vectors
def dotProductNormal(self, vec: 'SparseVector') -> int:
# Time: O(M)
prod = 0
for idx,val in self.vector.items():
if idx in vec.vector:
prod += val * vec.vector[idx]
return prod
# Return the dotProduct of two sparse vectors
# when only one of them is sparse
def dotProductFollowUp(self, vec: 'SparseVector') -> int:
# Time: O(min(M,N)) where M and N are length of the two vectors
prod = 0
vec1, vec2 = sorted([self,vec],key = lambda x: len(x.vector))
# iterate through the sparse one, whichever has smaller length
for idx,val in vec1.vector.items():
if idx in vec2.vector:
prod += val * vec2.vector[idx]
return prod
# Return the dotProduct of two sparse vectors
def dotProduct(self, vec: 'SparseVector') -> int:
# return self.dotProductNormal(vec)
return self.dotProductFollowUp(vec)
You don't have any submissions yet.
xxxxxxxxxxclass SparseVector {public: SparseVector(vector<int> &nums) { } // Return the dotProduct of two sparse vectors int dotProduct(SparseVector& vec) { }};// Your SparseVector object will be instantiated and called as such:// SparseVector v1(nums1);// SparseVector v2(nums2);// int ans = v1.dotProduct(v2);